import java.util.ArrayList;
import java.util.List;

public class MaxAreaOfIsland {
    static int m,n;
    static boolean f1,f2;
    static int[] dx={0,0,1,-1};
    static int[] dy={1,-1,0,0};
    static boolean[][] check;
    static boolean[][] visit;
    static List<List<Integer>> ret;
    static List<Integer> path;
    public static boolean dfs(int[][] heights,int i,int j){
        if((f1==true&&f2==true)||(check[i][j]==true)) return true;

        for(int k=0;k<4;k++){
            int x=i+dx[k],y=j+dy[k];
            if(x>=0&&y>=0&&x<m&&y<n&&heights[i][j]>=heights[x][y]&&visit[i][j]==false){
                f1=(x==0||y==0)?true:f1;
                f2=(x==m-1||y==n-1)?true:f2;
                visit[x][y]=true;
                if(dfs(heights,x,y)==true)
                {
                    return true;
                }
            }
        }
        return false;
    }
    public static List<List<Integer>> pacificAtlantic(int[][] heights) {
        ret=new ArrayList<>();
        path=new ArrayList();
        m=heights.length;
        n=heights[0].length;
        check=new boolean[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                f1=(i==0||j==0)?true:false;
                f2=(i==m-1||j==n-1)?true:false;
                visit=new boolean[m][n];
                visit[i][j]=true;
                if(dfs(heights,i,j)==true){
                    path.clear();
                    path.add(i);
                    path.add(j);
                    check[i][j]=true;
                    ret.add(new ArrayList(path));
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        int[][] grid = new int[][]{
                {1,2,2,3,5},
                {3,2,3,4,4},
                {2,4,5,3,1},
                {6,7,1,4,5},
                {5,1,1,2,4}
        };
        pacificAtlantic(grid);
    }
}
